package com.sk.leetcode.arithmetic.test1_10;

/**
 * 给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
 * '.' 匹配任意单个字符。
 * '*' 匹配零个或多个前面的元素。
 * 说明:
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 */
public class Test10 {
    public static void main(String[] args) {
//        int d = "sadasdawda".indexOf("da");
//        String s = "sssssa";
//        s = s.substring(s.length());
//        System.out.println(s);

        //boolean b = isMatch2("mississippi", "mis*is*p*.");
        //boolean b = isMatch2("", ".");
        //boolean b = isMatch2("a", "ab*a");
        // boolean b = isMatch2("abcdede", "ab.*de");
        boolean b = isMatch2("abaabababbcbcabbcbc", "b*ab.*.*.*.b..*");
        System.out.println(b);
    }

    /**
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch2(String s, String p) {
        if("".equals(p)) {
            if("".equals(s)) {
                return true;
            }
            return false;
        }
        String[] strings = p.split("");

        String[] reg = new String[strings.length];
        int index = 0;
        String value = "";
        for (int i = 0; i < strings.length; i++) {
            if(strings[i].equals(".")) {
                if(value.contains(".")) {
                    value += ".";
                    continue;
                }
                if(!"".equals(value)) {
                    reg[index++] = value;
                }
                value = ".";
                continue;
            }
            if("*".equals(strings[i])) {
                if(value.length() <= 1) {
                    reg[index++] = value + "*";
                } else {
                    String s1 = value.substring(0, value.length() - 1);
                    String s2 = value.substring(value.length() - 1, value.length());
                    reg[index++] = s1;
                    reg[index++] = s2 + "*";
                }
                value = "";
                continue;
            }
            if(value.contains(".")) {
                reg[index++] = value;
                value = "";
            }
            value += strings[i];
        }
        if(value.length() != 0) {
            reg[index++] = value;
        }

        Reg reS = new Reg();
        Reg reP = null;
        if(reg.length > 0) {
            for (int i = 0; i < index; i++) {
                if(i == 0) {
                    reS.setReg(reg[i]);
                    reP = reS;
                } else {
                    Reg re = new Reg();
                    re.setReg(reg[i]);
                    re.setPre(reP);
                    reP.setNext(re);
                    reP = re;
                }
            }
        }

        boolean b = true;
        Reg re = reS;
        while (b) {
            if(re.next() == null) {
                b = false;
                continue;
            }
            if(re.getReg().equals(".*")) {
                if(re.next().getReg().contains("*")) {
                    re.setNext(re.next().next());
                    if(re.next() != null) {
                        re.next().setPre(re);
                    }
                    continue;
                }
                re = re.next();
                continue;
            }
            if(re.getReg().contains("*")) {
                if(re.next().getReg().equals(".*")) {
                    re.setReg(".*");
                    re.setNext(re.next().next());
                    if(re.next() != null) {
                        re.next().setPre(re);
                    }
                    continue;
                }
                if(re.next().getReg().contains("*")) {
                    re.setReg(re.getReg() + re.next().getReg());
                    re.setNext(re.next().next());
                    if(re.next() != null) {
                        re.next().setPre(re);
                    }
                    continue;
                }
                re = re.next();
                continue;
            }
            re = re.next();
        }
        return jisuan(s, reS);


    }

    /**
     * "abaabababbcbcabbcbc"
     * "b*ab.*.*.*.b..*"
     * @param s
     * @param reg
     * @return
     */
    private static boolean jisuan(String s, Reg reg) {
        if(reg == null) {
            if(s.length() == 0) {
                return true;
            }
            return false;
        }
        if(reg.getReg().equals(".*")) {
            if(reg.next() == null) {
                return true;
            }
            if(reg.next().getReg().contains(".")) {
                if(s.length() < reg.next().getReg().length()) {
                    return false;
                }
                if(reg.next().next() == null) {
                    if(s.length() >= reg.next().getReg().length()) {
                        return true;
                    } else {
                        return false;
                    }
                } else {
                    Reg reg1 = reg.next().next();
                    if(reg1.getReg().equals(".*")) {
                        boolean b = jisuan(s.substring(reg.next().getReg().length()), reg1);
                        if(b) {
                            return b;
                        }
                    }
                    if(reg1.getReg().contains("*")) {
                        for (int i = reg.next().getReg().length(); i < s.length() + 1; i++) {
                            boolean b = jisuan(s.substring(i), reg1);
                            if(b) {
                                return b;
                            }
                        }
                    }
                }
                if(reg.next() != null) {
                    boolean b = jisuan(s, reg.next());
                    if(b) {
                        return b;
                    }
                }
            } else {
                String string = reg.next().getReg();
                boolean b1 = true;
                int inn = s.indexOf(string);
                if(inn < 0) {
                    return false;
                }
                String sp = s;
                while (b1) {
                    int inp = sp.indexOf(string);
                    sp = sp.substring(inp + string.length());
                    if(inp >= 0) {
                        Reg reg1 = reg.next().next();
                        if(reg1 == null) {
                            if(sp.length() == 0) {
                                return true;
                            }
                            continue;
                        }
                        boolean b = jisuan(sp, reg1);
                        if(b) {
                            return b;
                        }
                    } else {
                        b1 = false;
                    }
                }
            }
        }
        if(reg.getReg().contains("*")) {
            String s0 = reg.getReg().replaceAll("\\*", "");
            if(reg.next() != null) {
                boolean b = jisuan(s, reg.next());
                if(b) {
                    return b;
                }
            } else {
                if(s.length() == 0) {
                    return true;
                }
            }
            String[] strings = s0.split("");//ssippi
            String[] ss = s.split("");//s*p*.

            for (int i = 0, j = 0; (i < strings.length && j < ss.length); ) {
                if(strings[i].equals(ss[j])) {
                    if(reg.next() != null) {
                        boolean b1 = jisuan(s.substring(++j, s.length()), reg.next());
                        if(b1) {
                            return b1;
                        }
                    } else {
                        if(++j == ss.length) {
                            return true;
                        }
                    }
                } else {
                    i++;
                }
            }
        }
        if(reg.getReg().contains(".")) {
            if(reg.next() == null) {
                if(s.length() == reg.getReg().length()) {
                    return true;
                } else {
                    return false;
                }
            } else {
                if(s.length() >= reg.getReg().length()) {
                    boolean b1 = jisuan(s.substring(reg.getReg().length()), reg.next());
                    if(b1) {
                        return b1;
                    }
                } else {
                    return false;
                }

            }
        }
        String re = reg.getReg();
        if(s.length() < re.length()) {
            return false;
        }
        String[] res = re.split("");
        String[] ss = s.split("");
        for (int i = 0; i < res.length; i++) {
            if(!ss[i].equals(res[i])) {
                return false;
            }
        }
        if(reg.next() != null) {
            boolean b1 = jisuan(s.substring(reg.getReg().length()), reg.next());
            if(b1) {
                return b1;
            }
        } else {
            if(ss.length == res.length) {
                return true;
            }
        }
        return false;
    }

    /**
     * 特殊处理正则(误入歧途)
     *
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch1(String s, String p) {
        if("".equals(p)) {
            if("".equals(s)) {
                return true;
            }
            return false;
        }
        String[] strings = p.split("");
        if("*".equals(strings[0])) {
            return false;
        }

        String[] reg = new String[strings.length];
        int index = 0;
        String value = "";
        for (int i = 0; i < strings.length; i++) {
            if(strings[i].equals(".")) {
                if(!"".equals(value)) {
                    reg[index++] = value;
                }
                value = ".";
                continue;
            }
            if("*".equals(strings[i])) {
                if(value.length() == 1) {
                    reg[index++] = value + "*";
                } else {
                    String s1 = value.substring(0, value.length() - 1);
                    String s2 = value.substring(value.length() - 1, value.length());
                    reg[index++] = s1;
                    reg[index++] = s2 + "*";
                }
                value = "";
                continue;
            }
            value += strings[i];
        }
        if(value.length() != 0) {
            reg[index++] = value;
        }

        //List<Reg> list = new ArrayList<>();
        Reg reS = new Reg();
        Reg reP = null;
        if(reg.length > 0) {
            for (int i = 0; i < index; i++) {
                if(i == 0) {
                    reS.setReg(reg[i]);
                    reP = reS;
                } else {
                    Reg re = new Reg();
                    re.setReg(reg[i]);
                    re.setPre(reP);
                    reP.setNext(re);
                    reP = re;
                }
            }
        }
        boolean b = true;
        Reg reg1 = reS;
        while (b) {
            String r = reg1.getReg();
            if(r.equals(".*")) {
                if(reg1.next() == null) {
                    return true;
                }
                boolean bb = true;
                Reg r11 = reg1.next();
                int len = 0;
                while (bb) {
                    if(r11.getReg().contains("*")) {
                        if(r11.next() == null && s.length() >= len) {
                            return true;
                        }
                        r11 = r11.next();
                    } else if(reg1.getReg().equals(".")) {
                        if(r11.next() == null && s.length() >= len) {
                            return true;
                        }
                        len++;
                        r11 = r11.next();
                    } else {
                        reg1 = r11;
                        bb = false;
                    }
                }

                if(reg1.getReg().length() > s.length() - len) {
                    return false;
                }

                boolean b1 = true;
                String string = s;
                while (b1) {
                    int ind = s.indexOf(reg1.getReg());
                    if(ind == -1) {
                        return false;
                    }
                    string = s.substring(ind + reg1.getReg().length());


                    //s = s.substring(regl.length, s.length());
                }
                reg1 = reg1.next();
                if(reg1 != null) {
                    continue;
                } else {
                    if(s.length() == 0) {
                        return true;
                    }
                    return false;
                }
            }

            if(r.contains("*")) {
                boolean b1 = true;
                Reg reg2 = reg1;
                while (b1) {
                    if(reg2.next() == null) {
                        if(s.length() == 0) {
                            return true;
                        }
                        String[] split = s.split("");
                        String a = reg2.getReg().substring(0, 1);
                        for (String st : split) {
                            if(!st.equals(a)) {
                                return false;
                            }
                        }
                        return true;
                    }

                }


                if(reg1.next() == null) {
                    reg1 = reg1.next();
                    continue;
                }
                if(reg1.pre().getReg().equals(".*")) {
                    if(reg1.next() == null) {
                        return true;
                    }
                    reg1.setReg(".*");
                    reg1 = reg1.next();
                    continue;
                }


                if(reg1.pre().getReg().contains("*")) {
                    String a = reg1.pre().getReg().substring(0, 1);
                    boolean b2 = true;
                    while (b2) {
                        if(s.length() > 0) {
                            b2 = false;
                        } else {
                            boolean b3 = true;
                            Reg r1 = reg1.next();
                            while (b3) {
                                if(r1 == null) {
                                    return true;
                                } else {
                                    if(!r1.getReg().contains("*")) {
                                        return false;
                                    }
                                    r1 = r1.next();
                                }
                            }
                        }
                    }
                    reg1 = reg1.next();
                    continue;
                }

            }

            if(reg1.next() == null) {
                b = false;
            } else {
                reg1 = reg1.next();
            }
        }

        return true;
    }


    /**
     * 逻辑为正则截取匹配，考虑点非常多，复杂度比较高，还有很多bug
     *
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch(String s, String p) {
        if("".equals(p)) {
            if("".equals(s)) {
                return true;
            }
            return false;
        }
        String[] strings = p.split("");
        if("*".equals(strings[0])) {
            return false;
        }
        String[] reg = new String[strings.length];
        int index = 0;
        String value = "";
        for (int i = 0; i < strings.length; i++) {
            if(strings[i].equals(".")) {
                if(!"".equals(value)) {
                    reg[index++] = value;
                }
                value = ".";
                continue;
            }
            if("*".equals(strings[i])) {
                if(value.length() == 1) {
                    reg[index++] = value + "*";
                } else {
                    String s1 = value.substring(0, value.length() - 1);
                    String s2 = value.substring(value.length() - 1, value.length());
                    reg[index++] = s1;
                    reg[index++] = s2 + "*";
                }
                value = "";
                continue;
            }
            value += strings[i];
        }
        if(value.length() != 0) {
            reg[index++] = value;
        }

        boolean b = false;
        for (int i = 0; i < index; i++) {
            if(".*".equals(reg[i])) {
                b = true;
                continue;
            }
            if(reg[i].contains("*")) {
                if(b) {
                    continue;
                }
                int n = 0;
                String[] strs = s.split("");
                for (int j = 0; j < strs.length; j++) {
                    if(strs[j].equals(reg[i].substring(0, 1))) {
                        n++;
                    } else {
                        j = strs.length;
                    }
                }
                s = s.substring(n, s.length());
                continue;
            }
            if(b) {
                int in = s.lastIndexOf(reg[i].charAt(0));
                if(in < 0) {
                    return false;
                }
                s = s.substring(in + 1, s.length());
                b = false;
                continue;
            }
            if(s.length() == 0) {
                if(reg.length > i) {
                    return false;
                }
                if(".".equals(reg[i]) && reg.length == 1) {
                    return true;
                }
            }
            String[] strs = s.split("");
            String[] regs = reg[i].split("");
            if(regs.length > strs.length) {
                return false;
            }
            for (int j = 0; j < regs.length; j++) {
                if(!strs[j].equals(regs[j]) && !regs[j].equals(".")) {
                    return false;
                }
            }
            s = s.substring(regs.length, s.length());
            if(s.length() == 0 && reg.length == i + 1) {
                return true;
            }
        }
        if(b) {
            return b;
        }
        if(s.length() > 0) {
            return false;
        }
        return true;
    }


}

class Reg {
    private int n;
    private String reg;
    private Reg next;
    private Reg pre;

    public String getReg() {
        return reg;
    }

    public void setReg(String reg) {
        this.reg = reg;
    }

    public void setNext(Reg next) {
        this.next = next;
    }

    public void setPre(Reg pre) {
        this.pre = pre;
    }

    public Reg next() {
        return next;
    }

    public Reg pre() {
        return pre;
    }

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }
}